package zuosheng.stackandQueue;

import java.util.Stack;

/**
 * @author lj
 * @Description: 求矩阵的最大子矩阵面积
 * @date 2020-11-20 14:13
 * @QQ 851477108
 */

//单调栈的应用
public class MaxRecArea {
    //主函数，让二维数组转换成多层的一维数组，再根据一维数组构建直方图
    public int maxRecSize(int[][] map){
        if (map == null || map.length == 0 || map[0].length == 0){
            return 0;
        }

        int maxArea = 0;
        int[] height = new int[map[0].length];
        for (int i = 0; i < map.length; i++){
            for (int j = 0; j < map[0].length; j++){
                //如果j的位置为0，则将整个高度变为0，否则就在原来的长度基础上加1
                height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
            }
            //计算每次从第一行向下分层后每一次的最大面积
            maxArea = Math.max(maxRecFromBottom(height), maxArea);
        }
        return maxArea;
    }

    //数组表示直方图最大的面积
    public int maxRecFromBottom(int[] height){
        if (height == null || height.length == 0) {
            return 0;
        }

        int maxArea = 0;
        //单调栈
        Stack<Integer> stack = new Stack<>();
        //这个for循环遍历数组的每一个数
        for (int i = 0; i < height.length; i++) {
            //当栈不为空，且当前数小于等于栈顶
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                //第一次循环popIndex=0，L表示弹出之后底下的下标，如果没有东西则为-1.
                int popIndex = stack.pop();
                int Left = stack.isEmpty() ? -1 : stack.peek();
                int Right = i;
                //左边界为L，右边界为R，乘上弹出元素的位置上的高，求出弹出元素的最大面积
                int curArea = (Right-Left-1) * height[popIndex];
                //与之前的比较得到更大值
                maxArea = Math.max(maxArea, curArea);
            }
            //如果arr[i]值大于栈顶，直接压入
            stack.push(i);
        }
        //最后栈内可能还剩东西，这个while在结算栈中剩余的内容
        while (!stack.isEmpty()){
            //第一次循环popIndex=0，L表示弹出之后底下的下标，如果没有东西则为-1.
            int popIndex = stack.pop();
            int Left = stack.isEmpty() ? -1 : stack.peek();
            //还在栈中的元素的矩阵右位置必然是height.length，因为在元素右边没有比更埃的数，才会让他们还在栈中
            int Right = height.length;
            //左边界为L，右边界为R，乘上弹出元素的位置上的高，求出弹出元素的最大面积
            int curArea = (Right-Left-1) * height[popIndex];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}
